//
// Created by Tan Ke on 2024/1/20.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>


enum VisitState {
    NOT_VISITED,
    VISITED_AND_IN_PROGRESS,
    VISITED_AND_SUCCESS,
    VISITED_AND_FAILED,
};

struct Item {
    int courseNum;
    struct Item* next;
};

struct RecordMapItem {
    int courseNum;
    enum VisitState visitState;
    struct Item* next;
};

bool canFinishDFS(struct RecordMapItem* recordMap, int i)
{
    if (recordMap[i].visitState == VISITED_AND_SUCCESS) {
        return true;
    }
    if (recordMap[i].visitState == VISITED_AND_FAILED) {
        return false;
    }
    if (recordMap[i].visitState == VISITED_AND_IN_PROGRESS) {
        return false;
    }

    if (recordMap[i].visitState == NOT_VISITED) {
        recordMap[i].visitState = VISITED_AND_IN_PROGRESS;
    }

    enum VisitState state = VISITED_AND_SUCCESS;
    struct Item* node = recordMap[i].next;

    while (node != NULL) {
        if (canFinishDFS(recordMap, node->courseNum) == false) {
            state = VISITED_AND_FAILED;
            break;
        }
        node = node->next;
    }
    recordMap[i].visitState = state;
    return recordMap[i].visitState == VISITED_AND_SUCCESS;
}

bool canFinish(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize)
{
    struct RecordMapItem* recordMap = (struct RecordMapItem*)malloc(sizeof(struct RecordMapItem) * numCourses);
    for (int i = 0; i < numCourses; i ++) {
        recordMap[i].courseNum = i;
        recordMap[i].visitState = NOT_VISITED;
        recordMap[i].next = NULL;
    }

    for (int i = 0; i < prerequisitesSize; i++) {
        for (int m = 1; m < prerequisitesColSize[i]; m ++) {
            struct Item* node = (struct Item*)malloc(sizeof(struct Item));
            node->courseNum = prerequisites[i][m];
            node->next = recordMap[prerequisites[i][0]].next;
            recordMap[prerequisites[i][0]].next = node;
        }
    }

    for (int i = 0; i < numCourses; i ++) {
        if (canFinishDFS(recordMap, i) == false) {
            return false;
        }
    }
    return true;
}

int main(void)
{
    int **prerequisites = (int**)malloc(sizeof(int*) * 1);
    int *row = (int*)malloc(sizeof(int) * 2);
    row[0] = 0;
    row[1] = 1;
    prerequisites[0] = row;
    int *rowSize = (int*)malloc(sizeof(int));
    rowSize[0] = 2;

    printf("%d\n", canFinish(2, prerequisites, 1, rowSize));
    return 0;
}
